package org.example.基于堆实现;


import org.example.Priority;
import org.example.Queue;

/**
 * 基于 完全二叉树 实现优先级队列   时间复杂度为logn
 * @param <E>
 */
public class PriorityQueue4<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue4(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        int child = size++;
        int parent = (child -1)  / 2;
        while (child > 0 && e.priority() > array[parent].priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child -1)  / 2;
        }
        array[child] = e;
        return true;
    }


    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        // 交换
        swap(0, size - 1);
        E e = (E) array[size -1];
        size--;
        array[size - 1] = null; // help GC
        // 下潜
        down(0);
        return e;
    }

    /**
     * 下潜
     * @param parent
     */
    private void down(int parent) {
        int left = 2 * parent +1;
        int right = left + 1;
        int max = parent;
        if(left < size && array[max].priority() < array[left].priority()) {
            max = left;
        }
        if(right < size && array[max].priority() < array[right].priority()) {
           max = right;
        }
        if (max != parent) {
            swap(parent, max);
            down(max);
        }
    }

    /**
     * 交换
     * @param i
     * @param j
     */
    protected void swap(int i, int j) {
        Priority priority = array[i];
        array[i] = array[j];
        array[j] = priority;
    }


    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
